// 1,1,2,3,5,8,13...

// 暴力迭代，这种方法的算法复杂度是O(2^n)，太费性能
function stair(n) {
  if (n === 0) {
    return 1;
  } else if (n < 0) {
    return 0;
  } else {
    return stair(n - 1) + stair(n - 2)
  }
}

// 缓存计算好的值（for 循环） 自下往上 性能最好
function stair_2(n) {
  const arr = new Array(n);

  for (let i = 1; i <= n; i ++ ) {
    if (i === 1 || i === 2) {
      arr[i-1] = 1
    } else {
      arr[i-1] = arr[i-2] + arr[i-3]
    }
  }

  return n<=0 ? 0 : arr[n-1];

}

// 缓存计算好的值（迭代） 自上往下
function helper(arr,n) {
  if(n === 1 || n ===2) return 1;
  if(arr[n]) return arr[n];
  arr[n] = helper(arr,n-1) + helper(arr,n-2);
  return arr[n]
}

function stair_3(n){
  let arr = [];

  return helper(arr,n)
}



// console.time('stair');
// console.log(stair(40));
// console.timeEnd('stair');

console.time('stair_3');
console.log(stair_4(10));
console.timeEnd('stair_3');